#include<vector>
#include<algorithm>
#include<iostream>
using std::vector;



class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.size() < 3) return res;
        // 先进行排序
        std::sort(nums.begin(), nums.end());
        // 创建新数组去重, 0的话直接删到只剩一个
        vector<int> numsDedup;
        int zeroCount = 0;
        for (auto n : nums) {
            if (n != 0) {
                // 没有3个重复就行
                if (numsDedup.size() <= 1 || (numsDedup.size() > 1 && *(numsDedup.end()-2) != n))
                    numsDedup.push_back(n);
            }
            else {
                if (zeroCount == 0) numsDedup.push_back(0);
                else if (zeroCount == 2) {
                    
                    res.push_back({0, 0, 0});
                }
                zeroCount ++; 
            }
        }
        
        for (auto n: numsDedup) std::cout << n << " ";
        std::cout << "\n";
        for (int k = 1; k < int(numsDedup.size())-1; k++) {
            //双指针搜索
            std::cout << k << "\n";
            int i = 0, j = int(numsDedup.size())-1;
            if (k > 1 && numsDedup[k] == numsDedup[k-1]) i = k-1;
            while (i < k && j > k && i != -1 && j != -1) {
                auto sum = numsDedup[i] + numsDedup[j] + numsDedup[k];
                if (sum == 0) {
                    res.push_back({numsDedup[i], numsDedup[k], numsDedup[j]});
                    // i,j都向内移动
                    auto left = numsDedup[i], right = numsDedup[j];
                    while (numsDedup[i] == left) i++;
                    while (numsDedup[j] == right) j--;

                }
                else if (sum < 0) {
                    // 找到第一个使得 sum >= 0的值
                    i = this->find1sGreater(numsDedup, i, k, -numsDedup[k]-numsDedup[j]);
                }
                else {
                    j = this->find1stLess(numsDedup, k, j, -numsDedup[i]-numsDedup[k]);
                }
                
            }
        }
        // 给res去重
        return res;

    };

    int find1stLess(vector<int>& nums, int left, int right, int value){
        // 找到第一个小等于value值的索引，找不到返回-1
        if (right - left < 2) return -1;
        auto mid = (right + left) / 2;
        if (nums[mid] == value) return mid;
        else if (nums[mid] < value) {
            if (nums[mid+1] > value) return mid;
            else return this->find1stLess(nums, mid, right, value);
        }
        else {
            return this->find1stLess(nums, left, mid, value);
        }
    }

    int find1sGreater(vector<int>& nums, int left, int right, int value) {
        // 找到第一个大等于value值的索引
        if (right - left < 2) return -1;
        auto mid = (right + left) / 2;
        if (nums[mid] == value) return mid;
        else if (nums[mid] < value) {
            return this->find1sGreater(nums, mid, right, value);
        }
        else {
            if (nums[mid-1] < value) return mid;
            else return this->find1sGreater(nums, left, mid, value);
        }
    }
};

int main() {
    vector<int> input = {};
    int n;
    while (std::cin >> n) {
        input.push_back(n);
    }
    std::cout << "input: \n";
    for (auto k: input) std::cout << k << " ";
    std::cout << "\n";
    

    auto res = Solution().threeSum(input);
    std::cout << "triple tuple size: " << res.size() << "\n";
    for (auto v : res) std::cout << "[" << v[0] << "," << v[1] << "," << v[2] << "]\n";
    return 0;
}